//
//  132. 分割回文串 II.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/6.
//

import Foundation

//https://leetcode.cn/problems/palindrome-partitioning-ii/description/
//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
//
//返回符合要求的 最少分割次数 。
//
//
//
//示例 1：
//
//输入：s = "aab"
//输出：1
//解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
//示例 2：
//
//输入：s = "a"
//输出：0
//示例 3：
//
//输入：s = "ab"
//输出：1
//
//
//提示：
//
//1 <= s.length <= 2000
//s 仅由小写英文字母组成

func 分割回文串II(_ s: String) -> Int {
    let str = Array(s)
    let len = str.count
    if len <= 1 {
        return 0
    }
    //dpp[i][j] 记录 从i到j 是否为回文
    var dpp = Array(repeating: Array(repeating: false, count: len), count: len)
    let arr = Array(s)
    for i in 0 ..< len {
        dpp[i][i] = true
        if i < len - 1 {
            if arr[i] == arr[i + 1] {
                dpp[i][i + 1] = true
            }
        }
    }
    for c in 3 ..< len + 1 {
        for i in 0 ..< len - c + 1 {
            let l = i
            let r = i + c - 1
            if arr[l] == arr[r] {
                dpp[l][r] = dpp[l + 1][r - 1]
            }
        }
    }
    var dp = Array(repeating: len, count: len + 1)
    for i in 0 ..< len {
        if dpp[0][i] {
            //0~i是回文 那么不需要划分 比如 aab 当i为0或者1的时候
            dp[i] = 0
        } else {
            //0~i不是回文 那么z先默认要分割i次 比如 aab默认分割2次即 a a b 三个都是回文 默认为最差情况
            dp[i] = i
            //遍历从1~i
            for j in stride(from: 1, through: i, by: 1) {
                //如果从j到i是回文 尝试分割一次
                if dpp[j][i] {
                    dp[i] = min(dp[i], dp[j - 1] + 1)
                }
            }
        }
    }
    return dp[len - 1]
}

